package com.salim.leetcode.$72;

public class EditDistance {
    /**
     *   0 e x e c u t i o n
     * 0 0 1 2 3 4 5 6 7 8 9
     * i 1 1 2 3 4 5 6 6 7 8
     * n 2 2 2 3 4 5 6 7 7 7
     * t 3 3 3 3 4 5 5 6 7 8
     * e 4
     * n 5
     * t 6
     * i 7
     * o 8
     * n 9
     * 以in->executio=7步为例
     * 因为n!=o
     * in->executi=7步 从这一步增加o=8步
     * i->executi=6步 从这一步替换n变成o=7步
     * i->execitio=7步 从这一步删除n = 8步
     * 取最小的
     * 以i->executi=6步为例
     * 因为i=i
     * 那么i->executi的步数 = null->execut的步数即6
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        if(word1.length()==0){
            return word2.length();
        }else if(word2.length()==0){
            return word1.length();
        }

        int[][] matrix = new int[word1.length()+1][word2.length()+1];
        for(int i=0;i<word1.length()+1;i++){
            matrix[i][0] = i;
        }
        for(int j=0;j<word2.length()+1;j++){
            matrix[0][j] = j;
        }
        for(int i=1;i<word1.length()+1;i++){
            for(int j=1;j<word2.length()+1;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    //相等 取斜对角
                    matrix[i][j] = matrix[i-1][j-1];
                }else{
                    //不相等 三选一最小+1
                    matrix[i][j] = Math.min(matrix[i-1][j],Math.min(matrix[i-1][j-1],matrix[i][j-1]))+1;
                }
            }
        }
        return matrix[word1.length()][word2.length()];
    }
}
